package com.yehui.algorithm.sort.impl;

import com.yehui.algorithm.sort.IntArraySort;

/**
 * 归并排序
 */
public class MergeSort implements IntArraySort {

    /**
     * 排序
     *
     * @param source
     */
    @Override
    public void sort(int[] source) {
        dfsSort(source, 0, source.length - 1);
    }

    /**
     * 递归实现
     *
     * @param source
     * @param start
     * @param end
     */
    private void dfsSort(int[] source, int start, int end) {
        if(source == null || source.length == 0) {
            return;
        }

        if(start >= end) {
            return;
        }

        int mid = (start + end) / 2;
        int start1  = start;
        int end1 = mid;
        int start2 = mid + 1;
        int end2 = end;
        dfsSort(source, start1, end1);
        dfsSort(source, start2, end2);

        //merge
        int[] temp = new int[source.length];
        int index = start;
        while (start1 <= end1 && start2 <= end2) {
            temp[index++] = source[start1] < source[start2] ? source[start1++] : source[start2++];
        }
        while (start1 <= end1) {
            temp[index++] = source[start1++];
        }
        while (start2 <= end2) {
            temp[index++] = source[start2++];
        }
        for (int i = start; i < end + 1; i++) {
            source[i] = temp[i];
        }
    }

    /**
     * 迭代实现
     *
     * @param source
     */
    private void iterSort(int[] source) {
        if(source == null || source.length == 0) {
            return;
        }

        int window = 1;
        int[] temp = new int[source.length];
        int index = 0;
        for(; window <= source.length; window *= 2) {
            for (int start = 0; start < source.length; start += 2 * window) {
                int start1 = start;
                int end1 = Math.min((start + window), source.length);
                int start2 = end1;
                int end2 = Math.min((start + 2 * window), source.length);

                index = start1;
                while (start1 < end1 && start2 < end2) {
                    temp[index++] = source[start1] < source[start2] ? source[start1++] : source[start2++];
                }
                while (start1 < end1) {
                    temp[index++] = source[start1++];
                }
                while (start2 < end2) {
                    temp[index++] = source[start2++];
                }
                for (int i = start; i < end2; i++) {
                    source[i] = temp[i];
                }
            }
        }
    }
}
